package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/4 18:14
 *
 * 顺时针打印矩阵
 * 类似于搜索，维护vis和方向数组
 */


import java.util.ArrayList;

public class Main11 {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer>ans=new ArrayList<>();
        if(matrix[0].length==0)return ans;
        int n=matrix.length,m=matrix[0].length,cnt=1;
        int vis[][]=new int[n][m];
        int dx[]={0,1,0,-1};
        int dy[]={1,0,-1,0};
        int  dir=0;
        int x=0,y=0;
        vis[0][0]=1;
        while (cnt<n*m){
            while(true){
                int yy=y+dy[dir%4];
                int xx=x+dx[dir%4];
                //System.out.printf("(%d,%d),cnt=%d,vis=%d\n",xx,yy,cnt,vis[x][y]);
                if(yy<0||yy>=m||xx<0||xx>=n||vis[xx][yy]!=0)break;
                vis[x][y]=1;
                ans.add(matrix[x][y]);
                cnt++;
                x=xx;
                y=yy;
                //System.out.printf("(%d,%d),cnt=%d,val=%d\n",xx,yy,cnt,matrix[x][y]);
            }
            //改变方向
            dir++;
        }
        //走到终点后，直接退出循环了，还没加最后一个
        ans.add(matrix[x][y]);
        return ans;
    }


    public ArrayList<Integer> printMatrix2(int [][] matrix){
        ArrayList<Integer>ans=new ArrayList<>();
        if(matrix.length==0||matrix[0].length==0)return ans;
        //上下左右的边界值
        int up=0,down=matrix.length-1,left=0,right=matrix[0].length-1;
        while (up<=down&&left<=right){
            //每完成一步需要判断一次是否退出循环,否则会加重复
            //上向右,完成后缩小上边界
            for(int i=left;i<=right;++i){
                ans.add(matrix[up][i]);
            }
            up++;
            if(up>down)break;
            //右向下，完成后缩小右边界
            for(int i=up;i<=down;++i){
                ans.add(matrix[i][right]);
            }
            right--;
            if(right<left)break;
            //下向左，完成后缩小下边界
            for(int i=right;i>=left;--i){
                ans.add(matrix[down][i]);
            }
            down--;
            if(down<up)break;
            //左向上，完成后缩小左边界
            for(int i=down;i>=up;--i){
                ans.add(matrix[i][left]);
            }
            left++;
            if(left>right)break;
        }
        return ans;
    }
    public static void main(String[] args) {
        Main11 main11=new Main11();
        int [][]matrix={{1,2,3,1},{4,5,6,1},{4,5,6,1}};
        System.out.println(main11.printMatrix2(matrix));
    }
}
